A computer program listing appendix, incorporated herein by reference, is submitted as part of this disclosure. The computer program listing appendix is stored under the file name: xe2x80x9cAPPENDIX.TXTxe2x80x9d residing on one compact disk.
A portion of the disclosure of this patent document contains material, which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but other wise reserves all copyright rights whatsoever.
The present invention relates digital imaging. More specifically, the present invention relates to using texture mapping to create environmental projections for immersive video applications.
Texture mapping is typically used to add realism to graphic images. Generally, texture mapping involves mapping a two dimensional image, typically referred to as the texture map, onto an object. The texture map contains color information for the object. The texture map is divided into a plurality of texture elements or texels. Texels typically provide color information for the object. The object is divided into a plurality of facets. Each facet is typically a polygon having one or more picture elements (xe2x80x9cpixelsxe2x80x9d). The vertex of each facet is assigned a pair of texture coordinates which index the texture map to choose a texel (i.e., a color) from the texture map. The color of the facet is derived by interpolating between the colors and the vertices of the facet. Thus, the image of the texture map is reproduced onto the object.
At one time, the processing requirements of texture mapping limited texture mapping to professional graphic systems. However, as the processing power of microprocessors has increased, texture mapping software has become useable on consumer level computer systems. Furthermore, special graphics processing hardware capable of texture mapping has also become available for consumer level computer systems. Because texture mapping techniques have become feasible on consumer level computer systems, texture mapping techniques have been adapted for many different applications.
One use of texture mapping is environment mapping. Environment mapping uses computer graphics to display the surroundings or environment of a theoretical viewer. Ideally, a user of the environment mapping system can view the environment at any angle or elevation. FIG. 1 illustrates the construct used in conventional environment mapping systems. A viewer 105 (represented by an angle with a curve across the angle) is centered at the origin of a three dimensional space having x, y, and z coordinates. The environment of viewer 105 (i.e., what the viewer can see) is ideally represented by a sphere 110, which surrounds viewer 105. Generally, for ease of calculation, sphere 110 is defined with a radius of 1 and is centered at the origin of the three dimensional space. More specifically, the environment of viewer 105 is projected onto the inner surface of sphere 110. Viewer 105 has a view window 130 which defines the amount of sphere 110 viewer 105 can see at any given moment. View window 130 is typically displayed on a display unit for the user of the environment mapping system.
Conventional environment mapping systems include an environment capture system and an environment display system. The environment capture system creates an environment map which contains the necessary data to recreate the environment of viewer 105. The environment display system uses the environment map to display view window 130 (FIG. 1) to the user of the environment mapping system. Typically, the environment capture system and the environment display system are located in different places and used at different times. Thus, the environment map must be transported to the environment display system typically using a computer network, or stored in on a computer readable medium, such as a CD-ROM or DVD.
Computer graphic systems are generally not designed to process and display spherical surfaces. Thus, as illustrated in FIG. 2, texture mapping is used to create a texture projection of the inner surface of sphere 110 onto polygonal surfaces of a regular solid (i.e., a platonic solid) having sides that are tangent to sphere 110. Typically, as illustrated in FIG. 2, a texture projection in the shape of a cube 220 surrounds sphere 110. Specifically, the environment image on the inner surface of sphere 110 serves as a texture map which is texture mapped onto the inner surfaces of cube 220. A cube is typically used because most graphics systems are optimized to use rectangular displays and a cube provides six rectangular faces. Other regular solids (i.e., tetrahedrons, octahedrons, dodecahedrons, and icosahedrons) have non-rectangular faces. The faces of the cube can be concatenated together to form the environment map. During viewing, the portions of the environment map that correspond to view window 130 (FIG. 1 and FIG. 2) are displayed for viewer 105. Because, the environment map is linear, texture coordinates can be interpolated across the face of each cube based on the vertex coordinates of the faces during display.
An extension to environment mapping is generating and displaying immersive videos. Immersive video involves creating multiple environment maps, ideally at a rate of 30 frames a second, and displaying appropriate sections of the multiple environment maps for viewer 105, also ideally at a rate of 30 frames a second. Immersive videos are used to provide a dynamic environment rather than a single static environment as provided by a single environment map. Alternatively, immersive video techniques allow the location of viewer 105 to be moved. For example, an immersive video can be made to capture a flight in the Grand Canyon. The user of an immersive video display system would be able to take the flight and look out at the Grand Canyon at any angle.
Difficulties with immersive video are typically caused by the vast amount of data required to create a high resolution environment map and the large number of environment maps required for immersive video. Specifically, transmission and storage of the environment maps for high resolution flicker-free display may be beyond the processing capabilities of most computer systems.
Conventional data compression techniques have been used to compress the environment maps and reduce the amount of data transmitted or stored for immersive video. However, the additional processing time required to decompress a compressed environment map may impair the ability of the environment display system to process an adequate number of environment maps to provide a flicker-free display. Thus, there is a need for a compression and decompression method for immersive videos that minimizes the processing time required for decompressing the environment map.
The excessive data problem for immersive video is compounded by the inefficiencies of the conventional texture projections used to form environment maps. Specifically, although a cubic texture projection can provide realistic environment views, the cubic texture projection is not very efficient, i.e., the average amount of environment information per area is relatively low. The inefficiency of the cubic projection is caused by the lack of symmetry between the amount of spherical area on sphere 110 mapped onto cube 220. For example, if each surface of cube 220 is subdivided into equal square areas as illustrated in FIG. 3., the square areas do not map to equal areas of sphere 110. For conciseness and clarity, only cube face 220_1 of cube 220 is discussed in detail because each cube face of cube 220 is typically processed in the same manner. Specifically, in FIG. 3, cube face 220_1 is divided into N2 squares of equal area. More spherical area is mapped onto the squares near the center of a cube face than the squares near the edge of a cube face.
The inefficiency of the cubic texture projection is illustrated in FIG. 4. FIG. 4 uses a two dimensional mapping of a circle 410 onto a square 420. Specifically, a quarter of circle 410 is mapped onto each side of square 420. Arc segments 411-418 of circle 410 are mapped onto line segments 421-428 of square 420, respectively. Circle 410 is equivalent to sphere 110, square 420 is equivalent to cube 220, a side of square 420 is equivalent to a cube face of cube 220, each line segment of square 420 is equivalent to one of the square areas (FIG. 3) of cube 220, and each arc length of circle 410 is equivalent to the area of sphere 110 mapped on an area of cube 220. Like sphere 110, circle 410 has a radius of 1. Therefore, the arc length of an arc segment is equal to the angle of the arc segment in radians. Specifically, arc segment 414 has an arc length equal to angle A414 in radians. Angle A414 is equal to the inverse tangent of the length of facet 424 divided by the radius of circle 410. Thus, angle A414 and the arc length of arc segment 414 is equal to the inverse tangent of 0.25, which equals approximately 0.245. Angle A411 and the arc length of arc segment 411 are equal to the inverse tangent of 1 minus the inverse tangent of 0.75, which equals approximately 0.142. Thus, the mapping of circle 410 to square 420 results in inefficiencies due to the non-uniformity of the mapping.
Similarly, the mapping of sphere 110 onto cube 220 would result in mapping different amounts of spherical area of sphere 110 onto the equal areas of cube 220. For example, if a cube face is divided into 64 squares areas, a corner area would be mapped by only 0.0156 steradians (a measure of surface area) of sphere 120. However, a square area at the center of a cube face would be mapped by 0.0589 steradians of sphere 110. Thus, for the cubic texture projection, the area near the center of each face of cube 220 actually provides lower resolution than the square areas at the corners of each face. To provide the entire environment of viewer 105 in a consistent resolution, a display system using the cubic texture projection must typically conform to the lowest resolution area of the projection. Thus, the higher resolution areas are not used optimally, leading to inefficiencies.
In general, the ideal texture projection for environmental mapping would use facets that represent identically sized areas of the sphere, as well as identically shaped areas of the sphere. Furthermore, an equal sized areas in each facet should map to equal sized areas of the sphere. Moreover, the facets of the ideal texture projection would collectively cover the entire environment of viewer 105. However, no practical texture projection can satisfy all these criteria. As explained above, a low number of facets results in very low resolution display of the environment map. Hence, there is a need for an efficient texture projection for use with environment mapping and immersive videos.
Accordingly, the present invention provides efficient texture mapping schemes and compression schemes for environment mapping and immersive videos. In accordance with one embodiment of the present invention, polygonal curved surfaces are used in place of polygons as the facets of a texture projection. Specifically, a texture projection generation unit forms a texture projection by dividing the environment into a plurality of initial polygonal curved surfaces. The initial polygonal curved surfaces are subdivided to form a plurality of second-generation polygonal curved surfaces. The second-generation polygonal curved surfaces are further divided to form a plurality of third-generation polygonal curved surfaces. Division of polygonal curved surfaces continues until a plurality of last-generation polygonal curved surfaces is created. Each last-generation polygonal curved surface becomes a facet of the texture projection. Various division methods can be used to divide a polygonal curved surface. In accordance with one embodiment of the present invention, each polygonal curve of a specific generation has an equal area.
An environment map creation system uses the texture projection formed by polygonal curved surfaces to create an environment map. The environment map creation system includes an environment capture/generation unit that provides one or more images that captures the environment of a user. A corresponding image area on the one or more images is determined for each facet of the texture projection. Each facet is colored based on the corresponding image area. Each initial polygonal curved surface of the texture projection is converted into a two-dimensional polygonal image. The last-generation polygonal curved surfaces becomes pixels or texels of the two-dimensional image. The two-dimensional images are concatenated together to form the environment map.
A compression unit is used to compress the environment map and create a compressed environment map. Specifically, a compression unit in accordance with one embodiment of the present invention divides the environment map into a plurality of tiles. Each tile is compressed by a tile compressor independently of the other tiles to form a compressed tile. The sizes of the compressed tiles is used to create a header for the compressed environment map. In one embodiment of the present invention, the header contains an offset value for each compressed tile. The offset value provides the starting location of a compressed tile within the compressed environment map.
A decompression unit is then used to decompress a subset of relevant tiles of the environment map. The subset of relevant tiles includes all tiles which contain data needed to texture map a view window. The subset of relevant tiles may also include some tiles which do not have data needed to texture map the view window. Because only a portion of the tiles are actually decompressed, decompression units in accordance with the present invention requires less processing time than conventional decompression units.
After decompression of the subset of relevant tiles, an environment display system uses the newly formed decompressed environment map to texture map the view window. Specifically, the environment display system uses a texture projection having polygonal curved surfaces as an object to be texturized using the decompressed environment map. In some embodiments of the present invention, the polygonal curved surfaces are triangularized to take advantage of conventional hardware rendering units. By using an efficient texture projection with tiled compression and partial decompression, the environment maps created by embodiments of the present invention are ideally suited for immersive video applications.